package com.kingwood.algorithm.test200;

import java.util.*;

/**
 * @Author 22025812
 * @Description: LRU 相关
 * @Date: 2024/3/7 13:13
 * @Modified By：
 * @Version 1.0
 */
public class LRU {

    static class FileNode {
        String fileName;
        int fileSize;
        int frequency;  // 文件访问次数从小到大排序
        long lastAccessTime; // 从小到大排序
        public FileNode(String fileName, int fileSize) {
            this.fileName = fileName;
            this.fileSize = fileSize;
            this.frequency = 0;
            this.lastAccessTime = 0;
        }
    }

    /**
     * 文件缓存系统
     * https://fcqian.blog.csdn.net/article/details/135024413
     */
    static class FileLruCache {
        HashMap<String, FileNode> fileMap = new HashMap<>();
        int capacity;
        int currentCapacity;
        int sumFrequency;
        public FileLruCache(int capacity) {
            this.capacity = capacity;
            this.currentCapacity = 0;
            this.sumFrequency = 0;
        }

        /**
         * @param fileName 对应本题的文件名
         */
        public void get(String fileName) {
            // 如果文件不存在，则不作任何操作。
            if (!this.fileMap.containsKey(fileName)) {
                return;
            }

            FileNode fileNode = this.fileMap.get(fileName);
            fileNode.lastAccessTime = System.currentTimeMillis();
            fileNode.frequency++;
            this.sumFrequency++;
        }

        public void put(String fileName, int fileSize) {
            // 如果文件不存在，则创建文件节点。
            if (this.fileMap.containsKey(fileName)) {
                return;
            }

            if (currentCapacity + fileSize > capacity) {
//                System.out.println("超出文件缓存大小限制！");
                List<FileNode> list = new ArrayList<>(fileMap.values());
                list.sort((o1, o2) -> {
                    if (o1.frequency == o2.frequency) {
                        return Long.compare(o1.lastAccessTime, o2.lastAccessTime);
                    }
                    return Integer.compare(o1.frequency, o2.frequency);
                });

                int index = 0;
                while (!this.fileMap.isEmpty() && currentCapacity + fileSize > capacity) {
                    FileNode curFile = list.get(index);
                    currentCapacity -= curFile.fileSize;
                    fileMap.remove(curFile.fileName);
                    index++;
                }
            }

            this.fileMap.put(fileName, new FileNode(fileName, fileSize));
            this.currentCapacity += fileSize;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int lruCacheSize = Integer.parseInt(scanner.nextLine());
        int operationTimes = Integer.parseInt(scanner.nextLine());

        FileLruCache lruCache = new FileLruCache(lruCacheSize);
        for (int i = 0; i < operationTimes; i++) {
            String[] operation = scanner.nextLine().split(" ");
            String op = operation[0];
            String fileName = operation[1];

            if ("put".equals(op)) {
                int fileSize = Integer.parseInt(operation[2]);
                lruCache.put(fileName, fileSize);
            } else {
                lruCache.get(fileName);
            }
        }

        if (lruCache.fileMap.size() <= 0) {
            System.out.println("NONE");
        } else {
            // 否则取出文件系统中的文件名，按照字典序输出
            StringJoiner sj = new StringJoiner(",");
            lruCache.fileMap.keySet().stream().sorted().forEach(sj::add);
            System.out.println(sj);
        }
    }
}
